异质性联邦学习综述

隐私计算研习社 2022-09-24

The following article is from 狗熊会 Author 汤惠云

随着数据成为生产要素之一，人们对数据隐私和安全保护的需求也日益高涨。联邦学习（Federated learning）的提出正好呼应了这一需求。在联邦学习的框架下，各数据拥有方（称为client）无需上传他们的原始数据便可以协作解决机器学习问题。但是由于参与训练的数据是散落在各地的，不像分布式学习对数据有集中后打乱再分配的过程，因而联邦学习中天然存在数据异质性（non-IID Data）的问题。联邦学习中的数据异质性主要起源于一个client对应某特定的用户、特定的地理位置或特定的时间窗口。因此，各client的数据附有他们自己独特的属性。

0
引言假设考虑有监督学习的情形，的数据服从分布，数据异质性是指。根据式子，我们可以进一步考量异质性的缘由。

特征的分布有偏（covariate shift）：指各client间的分布一样，而的边际分布不一样。比如对于手写体，书写相同单词的用户由于书写习惯不一样，笔划力度、宽度、倾斜度很可能不尽相同。
标签的分布有偏（prior probability shift）：指各client间的分布一样，而的边际分布不一样。例如client按地域划分时，标签的分布在client间也许差别很大——袋鼠只生活在澳大利亚或公园；不同地域的人的面部特征、口音不一样。
相同的标签，不同的特征（concept shift）：指各client间的分布一样，而条件分布不一样。这是因为同样的标签在不同的client上可能对应不同的特征。比如由于文化风俗、气候条件、生活习惯等，各地的房屋、服饰风格极不相同。即使同一个标签，在不同的时段和时间尺度上也会有一些差异，比如同一条街道，秋天铺满落叶，冬天则覆盖着冰雪。
相同的特征，不同的标签（concept shift）：指各client间的分布一样，而条件分布不一样。例如由于用语习惯的差异，在输入法中，给定已有的字符，用户要输入的下一个字符很有个人色彩。

真实世界中的联邦数据集可能混合有上述的各种情形。同时真实世界分区数据集中跨client数据差异的表征也是一个重要的开放性问题。文献中最常见的合成non-IID数据的做法是构造标签的有偏分布，即对不同的client分配不同的标签。更好地理解真实世界中异质性数据的本质有利于构造更贴合实际的non-IID数据，以用来测试算法并评估其对不同程度异质性的适应性。

2异质性的影响从算法角度而言，数据异质性的存在违背了常见的算法（如SGD）对样本IID的假设，这就会导致一些经典的联邦学习算法（如FedAvg）在训练中用于更新模型的梯度是有偏差的，从而不利于算法结果的收敛，而且在极端异质的情况下，结果甚至不收敛。算法的结果自然会影响模型的表现。

从模型角度而言，异质性使得局部模型的最优参数一定程度上偏离全局模型的最优参数，这就使得共享的全局模型的适用性成了问题。包括把全局模型部署于各个客户端时，在客户端数据上的预测表现可能不尽如人意；或者在有些客户端上表现得好，有些客户端上表现却很差，从而导致不公平现象；或者应用于未参与联邦训练的客户端时泛化性能不佳。

3
异质性的解决1. 数据增强
既然异质性问题是源于各client数据分布的差异，于是有学者提出用数据增强的方法使得各client的数据更相似。例如Tongzhou Wang等人提议创建一小块可全局共享的公共数据集，该数据可以来自于公开数据源，或者各client不带隐私敏感信息的数据，以及对原始数据的提炼。

2. 异质性调整的联邦学习

联邦学习的原始目标是联合各client训练单个全局模型。在异质性条件下，实现这一目标存在困难。比较自然的解决方法是对已有的全局模型算法做一些更改与修补，比如不同的超参数选择，或者直接使用新的算法以建立更有效的全局模型，以适应一定程度的异质性。

异质性情况下，每个client的数据服从分布，并且局部目标函数为

其中是模型在样本上的损失。联邦学习的优化目标是最小化

令，。

已有文献对异质性联邦学习优化算法的理论分析除了一般性的要求损失函数Lipschitz连续，随机梯度的方差有界外，还会对数据的差异性施加一定的条件，例如约束client端的梯度和全局梯度间的差异，或者限制client端最优值和全局最优值间的差异。在这些约束条件下，Yu等人说明了局部SGD算法的误差的上界在non-IID情形下变差，为了达到（假设目标函数非凸）的收敛速度，局部更新次数K应小于，而不是IID情形下的。表1给出数据非独立同分布下各改进算法所需要的假设以及收敛速度的对比结果。下面介绍几种常见的改进的全局模型方法。

（1）限制client端最优值和全局最优值间的差异

Li 等人[5]提出往各client的局部目标函数中添加一约束项（如（2）所示），其中为超参数，通过调节的大小以适应不同程度的异质性，当取0时，即是FedAvg的目标函数。

（2）降低梯度方差

对一阶优化算法而言，使用动量方法和方差降低技术能有效提高优化和泛化表现。当存在异质性时，各client间的梯度差异往往比较大，此时适当降低局部更新的梯度的方差将有助于提高全局模型的收敛速度。但是关于如何将动量或方差降低技术纳入局部SGD和联邦平均算法中，学术界仍然没有达成共识。

Karimireddy等人[5]指出在异质性情况下，各client的解的路径都朝着各自最优解的方向前进，此时FedAvg方法下所计算的和真实的全局模型的最优解之间存在偏差，并提出引入控制变量调整局部梯度的方向，从而减小局部梯度间的方差，使得局部解的路径能朝着全局最优解的方向，最终加快算法的收敛速度。

至于动量方案，Yu等人建议让每个客户端维护一个局部动量缓冲区，并在每个通信回合中平均这些局部缓冲区以及局部模型参数。虽然这种方法从经验上提高了本地SGD的最终精度，但它需要加倍的通信成本。Wang等人提出了另一种称为SlowMo的动量方案，该方案可以在不牺牲吞吐量的情况下显著提高局部SGD的优化和泛化性能。Hsu等人提出了一个类似于SlowMo的动量方案。虽然[4,8]都表明，局部SGD的动量变量可以以与同步小批量SGD相同的速度收敛到非凸目标函数的平稳点，但在联邦学习环境中，证明动量加速收敛速度很有挑战性。

（3）修改全局模型的目标分布

Mohri等人指出若将各个客户端的数据视为不同的源分布，朴素的联邦学习相当于以各分布求平均得到一个目标分布，也就是将全局模型的目标分布刻画为，其中为client k的数据分布。但是基于信息量通常集中在少数人手中这一现象，直接对多源分布求均值得到的目标分布而求解未必足够好，且模型训练所基于的数据分布和泛化时真实的目标分布可能存在偏差。因此作者提出将目标分布视为多源分布的一个凸组合，即，然后转化成一个min-max问题，最优化使模型最劣的那个凸组合分布上的性能。损失函数为：

其中是的经验形式。惩罚项限制模型的复杂度以及分布的偏态。通过最优化权重，该算法能确保所得模型在最不利的分布下的泛化效果不至于太差。但是这篇文章事实上仍未解决目标分布到底是什么这个问题，而是提供了一个比较保守的解。这一类问题与多源自适应比较相关。

（4）修改局部模型参数的权重

同样为了解决异质性情况下全局模型的泛化效果在各client上好坏不一的问题，Li等人提出对于表现较差的client在训练时对其模型参数给予更高的权重，从而让全局模型在各client上的准确率分布更均匀，全局损失函数为

其中。

表1. Non-IID理论分析假设以及各异质性调整的联邦学习算法收敛速度

3. 个性化联邦学习

但是既然我们有能力基于每个client的本地数据进行训练，那么训练单个全局模型就一定是正确的目标吗？当然在许多情况下单个全局模型是有好处的，比如为没有数据的client提供模型。但是既然本地训练是可行的，那么各个client也能够训练得到自己的定制化模型，称为个性化联邦学习。个性化联邦学习是一种“多模型”的方法，旨在联合训练中为不同的client有效地学习出不同的模型。在异质性情况下，个性化方法往往可能比共享的全局模型取得更好的表现。下面介绍几种常见的个性化方法。

（1）多任务学习（Multi-Task Learning）

如果把一个client的本地学习问题（基于本地数据训练机器学习算法）当作一个任务的话，那么联邦学习可以类比于多任务学习的过程。多任务学习的结果是为每个任务学习一个特定的模型。因此大多数多任务学习算法要求所有的client参与到每一轮的训练中，这就使得该方法对cross-device（client为数量众多的手机等终端）情形不太适用。多任务学习捕捉任务间的相似性，得到一个任务相似性图。对联邦学习而言，任务关系图还可以作为通信图，对一个客户端来说，它在更新模型时与其任务相关性高的客户端通信，进行协作学习，减少与不相关客户端的通信。Smith 等人首先建立了联邦学习和多任务学习的关系，以多任务学习方法来处理联邦学习中的异质性困难。联邦多任务学习的一般模型框架如（4）所示：

其中表示通讯轮次，表示在第轮通讯时参与训练的client个数，表示由各client参数向量构成的二维矩阵，为任务间的关系矩阵。

（2）局部微调（Local Fine Tuning）和元学习（Meta-Learning）

局部微调是指首先联合学习一个全局模型，然后部署到客户端上，再由各个客户端基于本地数据进行额外的训练，得到个性化的模型。

给定一个训练好的全局模型，如何把该全局模型进行个性化？其中一种方法便是借助元学习的概念。元学习是模型调整的一种流行范式。在标准的Meta-learning 中，假设多个任务分布背后有一个潜在的元分布。通过挖掘这个元分布的信息来帮助在新任务上进行学习。对应到联邦学习中，各个客户端的数据对应不同的任务分布（由数据收集/采样引起的），期望全局模型拟合这些任务分布背后潜在的元分布。标准的联邦学习事实上就等于是在学习这个背后的潜在分布。Model-agnostic meta-learning (MAML)是一种经典的meta-learning方法，它期望得到一个能快速适应到新任务的全局模型。Chen等人在文章Federated meta-learning with fast convergence and efficient communication中将MAML应用到FL场景中，利用MAML得到一个全局模型，之后每个客户端把该全局模型作为本地训练的初始化，经过一步或几步梯度更新后得到表现良好的本地模型。Fallah等人在Chen等人工作的基础上进一步为此种方法提供了收敛性等方面的理论保证。结合MAML的FL目标函数如下所示：

其中表示梯度下降中的步长。的目标函数为

对式求梯度，

其中的无偏估计为

MAML-FL算法借鉴了FedAvg算法框架，即通过迭代训练完成，在每一轮的通讯迭代中，挑选一定比例的client参与训练，把上一轮求解得到的参数发送给这些client，由client进行本地更新步，每一步中，计算如式：

其中为局部学习率，，和为独立的batch，

最后各client把上传给server进行平均作为下一次迭代的初始值，迭代次后得到meta模型。

（3）模型插值

联邦学习中在共同训练全局模型的同时各client也在训练自己的本地模型，因此一个自然而然的想法便是对全局模型与本地模型进行插值从而得到各个client的个性化模型，即。令为全局模型，为client k的本地模型，为client k的插值权重，，，那么，该个性化的目标函数为

（4）用户聚类

还有一种个性化方法是把client聚成好几个类，每个类训练一个全局模型作为该类所有client的个性化模型。通常在训练中，所有client一边学习他们所属的类别一边学习各类的全局模型，其优化目标为：

其中为预设的表示重要性的指标，可以为或.

4. 丰富的特征工程

有些情况下通过添加用户和上下文情境的特征信息同样也能让共享的全局模型实现个性化的效果。比如事先提到的输入法单词预测的问题，即基于用户的已有输入内容预测其下一个要输入的单词，由于每个用户的用语习惯不一，有必要考虑个性化措施以提高预测效果。此时，除了把用户的已打字内容作为全局模型的输入，还可以考虑添加用户方面的特征，比如该用户最常使用的单词是什么？他正在使用什么app？以及上下文语境信息，例如聊天场景中，该用户方才发送了什么信息？通过如此一些恰当的特征工程，也能使得全局模型达到不错的个性化用户定制预测效果。然而，由于很少有公开数据集包含这样的特征，设计此类能为不同任务有效纳入环境信息的模型架构，以提高联邦学习所得模型的效用仍是一个重要的开放问题。

个性化联邦学习是一个新的方向，其中有诸多待解决的公开问题：

文献中观测到的个性化准确率比全局准确率高说明了个性化方法对FL的重要性。但是，用何指标来度量个性化方法的表现仍是一个需要考虑的问题。已有文献基本使用所有client个性化模型的平均准确率来衡量个性化方法的优劣，但是平均准确率高的个性化方法其性能不一定全面，例如，不一定在所有client上都取得同等的提升，即不一定公平。因此，Divi等人构造了多种指标从各方面度量个性化方法在预测提升上的表现以及在公平性上的表现。
Jiang等人强调了这样一个事实，同样结构和表现的模型，由于训练方式不同，在个性化能力上差异可能很大。尤其是，以最大化全局表现为目标来训练模型实际上可能会有损所得模型后续的个性化能力。要理解这其中缘由不但要从FL更要从更广泛的ML入手。
FL中的许多挑战诸如个性化和隐私问题都是在多任务/LTL框架下来进行研究的。那其他问题，比如concept drift，有没有可能也用这个框架来进行分析，例如作为一个终身学习的问题？
一些非参的迁移LTL算法，比如ProtoNets，能否用于FL？

4
什么情况下联邦全局模型更优？不同的异质性产生机制需要不一样的解决方案。例如在特征分布有偏的情形下，尽管各client的的边际分布有所差异，但是相同的，此时协作训练一个全局模型（global model）以学习倒不失为一个合适的办法。而当各client相同的特征却映射到不同的标签时，一些个性化方法可能更适宜用来学习真正的标签生成函数。

什么是联邦学习可实现而在本地机器上的局部训练所无法实现的？当局部数据集量小且数据是IID分布时，FL具有明显优势，而且联合训练一个全局模型也有利于FL的实际应用。另一方面，假设数据是non-IID分布的（例如在client间不一样），拟合局部模型可能更适合。因此，一个自然而然的理论问题便是决定在何种条件下共享的全局模型优于本地单独训练的模型。假设我们用client k拥有的个样本训练得到模型，我们能保证由联邦学习训练得到的模型在应用于client k时，准确性至少不亚于吗？我们能够量化联邦学习能带来多大的提升吗？我们能开发出在理论上保证和的效果至少相近的个性化策略吗？这其中的一些问题与之前关于多源自适应和不可知联邦学习的研究有关。

【参考文献】
[1] Kairouz P, McMahan H B, Avent B, et al. Advances and open problems in federated learning[J]. Foundations and Trends® in Machine Learning, 2021, 14(1–2): 1-210.
[2] Li X, Huang K, Yang W, et al. On the convergence of fedavg on non-iid data[J]. arXiv preprint arXiv:1907.02189, 2019.
[3] Tongzhou Wang, Jun-Yan Zhu, Antonio Torralba, and Alexei A Efros. Dataset distillation. arXiv preprint arXiv:1811.10959, 2018.
[4] Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization. arXiv preprint arXiv:1905.03817, 2019.
[5] Li T, Sahu A K, Zaheer M, et al. Federated optimization in heterogeneous networks[J]. Proceedings of Machine Learning and Systems, 2020, 2: 429-450.
[6] Karimireddy S P, Kale S, Mohri M, et al. Scaffold: Stochastic controlled averaging for federated learning[C]//International Conference on Machine Learning. PMLR, 2020: 5132-5143.
[7] Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. SlowMo: Improving communicationefficient distributed SGD with slow momentum. arXiv preprint arXiv:1910.00643, 2019.
[8] Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.06335, 2019.
[9] Mohri M, Sivek G, Suresh A T. Agnostic federated learning[C]//International Conference on Machine Learning. PMLR, 2019: 4615-4625.
[10] Li T, Sanjabi M, Beirami A, et al. Fair resource allocation in federated learning[J]. arXiv preprint arXiv:1905.10497, 2019.
[11] Smith V, Chiang C K, Sanjabi M, et al. Federated multi-task learning[J]. Advances in neural information processing systems, 2017, 30.
[12] Chen F, Luo M, Dong Z, et al. Federated meta-learning with fast convergence and efficient communication[J]. arXiv preprint arXiv:1802.07876, 2018.
[13] Jiang Y, Konečný J, Rush K, et al. Improving federated learning personalization via model agnostic meta learning[J]. arXiv preprint arXiv:1909.12488, 2019.
[14] Fallah A, Mokhtari A, Ozdaglar A. Personalized federated learning: A meta-learning approach[J]. arXiv preprint arXiv:2002.07948, 2020.
[15] Mansour Y, Mohri M, Ro J, et al. Three approaches for personalization with applications to federated learning[J]. arXiv preprint arXiv:2002.10619, 2020.
[16] Deng Y, Kamani M M, Mahdavi M. Adaptive personalized federated learning[J]. arXiv preprint arXiv:2003.13461, 2020.
[17] Kangkang Wang, Rajiv Mathews, Chloe Kiddon, Hubert Eichner, Franc¸oise Beaufays, and Daniel Ramage. ´Federated evaluation of on-device personalization. arXiv preprint arXiv:1910.10252, 2019.
[18] Divi S, Lin Y S, Farrukh H, et al. New metrics to evaluate the performance and fairness of personalized federated learning[J]. arXiv preprint arXiv:2107.13173, 2021.